package A一周刷爆LeetCode.B基础提升.CKMP与Manacher算法;

/**
 * @author wei.zhao
 * @description: KMP算法
 * @date 2022年08月19日 17:13
 */
public class Code01_KMP {

    public static void main(String[] args) {
        String str = "abcabcababaccc";
        String match = "ababa";
        System.out.println(getIndexOf(str, match));
    }

    public static int getIndexOf(String str, String match) {
        if (str == null || match == null || match.length() < 1 || str.length() < match.length()) {
            return -1;
        }
        char[] chars1 = str.toCharArray();
        char[] chars2 = match.toCharArray();
        int n = 0;
        int m = 0;
        int[] nextArr = getNextArr(chars2);
        while (n < chars1.length && m < chars2.length) {
            if (chars1[n] == chars2[m]) {
                n++;
                m++;
            } else if (nextArr[m] == -1) {
                n++;
            } else {
                m = nextArr[m];
            }
        }
        return m == chars2.length ? n - m : -1;
    }

    public static int[] getNextArr(char[] chars) {
        if (chars.length == 1) {
            return new int[]{-1};
        }
        int[] result = new int[chars.length];
        result[0] = -1;
        result[1] = 0;
        int i = 2;
        int c = 0;
        while (i < chars.length) {
            if (chars[i - 1] == chars[c]) {
                result[i++] = ++c;
            } else if (c == 0) {
                result[i++] = 0;
            } else {
                c = result[c];
            }
        }
        return result;
    }

}
